package 并查集;

public class QuickUnion extends UnionFind{

	public QuickUnion(int capacity) {
		super(capacity);
	}
	
	/**
	 * O(logn)
	 */
	@Override
	public int find(int v) {
		rangeCheck(v);
		while (v != parents[v]) {
			v = parents[v];
		}
		return v;
	}
	
	/**
	 * O(logn)
	 */
	@Override
	public void union(int v1, int v2) {
		int p1 = find(v1);
		int p2 = find(v2);
		if (p1 == p2) return;
		
		parents[p1] = p2;
		
	}

}
